#include <iostream>
#include <stack>


using namespace std;


// 中缀表达式转后缀表达式
// 1、从左到右扫描中缀表达式
// 2、遇到操作数时，将其输出
// 3、遇到运算符时，比较其与栈顶运算符的优先级
// 4、如果优先级比栈顶运算符的高，将运算符压入栈中
// 5、如果优先级低于或等于栈顶运算符的优先级，从栈中取出栈顶运算符，将运算符输出，并将当前运算符压入栈中
// 6、重复步骤2至5，直到表达式的最右边
// 7、将栈中剩余的运算符依次弹出输出

bool cmp_pri(char cur_ch, char top_ch) {
    if ((top_ch == '+' || top_ch == '-') && (cur_ch == '*' || cur_ch == '/'))
    {
        return true;
    }

    if ((top_ch == '(') && (cur_ch != ')'))
    {
        return true;
    }
    
    return false;
}

bool condition(char ch) {
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')')
    {
        return true;
    }
    return false;
}

string middletoendexpr(string infix) {
    string result;
    stack<char> s;
    for (char ch : infix)
    {
        cout << "current ch is " << ch << endl;
        // 如果是 0-9的数字直接入到结果栈中
        if (!condition(ch))
        {
            result.push_back(ch);
            continue;
        }
        // 如果是符号，则判断是否进入符号栈还是入到结果栈
        else
        {
            // 如果是左括号，直接入符号栈
            if (ch == '(')
            {
                s.push(ch);
                cout << "s push ch is '(' "<< endl;
                continue;
            }
            // 如果是右括号，将符号栈中的运算符依次出栈，直到遇到左括号
            if (ch == ')')
            {
                cout << "ch is ')' "<< endl;
                while (s.top() != '(')
                {
                    result.push_back(s.top());
                    cout << "result.push_back(s.top()) s.top() is " << s.top() << endl;
                    s.pop();
                }
                cout << "s.top() is " << s.top() << endl;
                s.pop();
                continue;
            }
            if (s.empty())
            {
                cout << "s is empty" << endl;
                s.push(ch);
                continue;
            }
            
            // 如果是运算符，判断优先级
            // 如果待输入的运算符优先级高于符号栈的栈顶元素，则入符号栈，否则入结果栈
            if (cmp_pri(ch, s.top()))
            {
                cout << "cmp_pri(ch, s.top()) is true s.top() is " << s.top() << endl;
                s.push(ch);
                continue;
            }
            else
            {
                while (!s.empty() && !cmp_pri(ch, s.top()))
                {
                    result.push_back(s.top());
                    s.pop();
                }
                s.push(ch);
                continue;
            }
        }   
    }

    
    // 处理栈中剩余的运算符
    while (!s.empty())
    {
        result.push_back(s.top());
        s.pop();
    }

    return result;
}



int main(int argc, const char** argv) {
    cout << middletoendexpr("1+2*3") << endl;
    cout << middletoendexpr("(1+2)*(3+4)") << endl;
    cout << middletoendexpr("1+(4+6)*2+8/2") << endl;
    return 0;
}